#include <iostream>
#include <vector>
#include <string>

using namespace std;

int centerIsEle(string s, int i){
    for(int j = 1; i-j >= 0; j++){
        if(s[i+j] != s[i-j]){
            return -1;
        }
    }
    return s.size()-i*2-1;
}

int centerIsLine(string s, int i){
    int j = i-1;
    for(int n = 0; j-n >= 0; n++){
        if(s[i+n] != s[j-n]){
            return -1;
        }
    }
    return s.size()-i*2;
}

string getString(string s, int num){
    string t;
    for(int i = 1; i <= num; i++){
        t += s[s.size()-i];
    }
    return t + s;
}

string shortestPalindrome(string s) {
    int r = s.size()%2, i = s.size()/2, e = -1, l = -1;
    for( ; i >= 0; i--){
        if(r){
            e = centerIsEle(s, i); if(e != -1) break;
            l = centerIsLine(s, i); if(l != -1) break;
        }else{
            l = centerIsLine(s, i); if(l != -1) break;
            e = centerIsEle(s, i>0 ? i-1 : 0); if(e != -1) break;
        }
    }
    return e == -1 ? getString(s, l) : getString(s, e);
}

int main(){
    string s = "aacecaaa";
    cout << shortestPalindrome(s) << endl;
    return 0;
}
